# -*- coding: utf-8 -*-
"""Controlador de Afds Optimizados"""

from tg import expose, flash, require, url, request, redirect
from pylons.i18n import ugettext as _, lazy_ugettext as l_
from tgext.admin.tgadminconfig import TGAdminConfig
from tgext.admin.controller import AdminController, AdminConfig
from repoze.what import predicates
from tg import tmpl_context, validate
from webhelpers import paginate
from sqlalchemy import func
from sqlalchemy.exc import IntegrityError, SQLAlchemyError
import transaction

from networkx import graphviz_layout
import pydot
import networkx as nx
#import matplotlib.pyplot as plt
import random

from lex.lib.base import BaseController
from lex.model import metadata, DBSession
from lex.model.model import AnalizadorLexico, ExpresionRegular, Afn, Afd
from lex import model
from lex.controllers.pila_cola import Pila, Cola

precedencia = {
              "*" : 10,
              "+" : 10,
              "?" : 10,
              "." : 9,
              "|" : 8,
              "(" : -1,
              ")" : -1,
              }

__all__ = ['AfdsopsController']

class AfdsopsController(BaseController):

    @expose('lex.templates.afdsops.generar_afdsops')
    def generar_afdop(self, id_analizador_lexico, page=1):
        """Metodo para generar el AFD Optimizado del analizador seleccionado"""
        try:
################################################################################
#Advertencia: Este proceso tambien se realiza en la funcion "generar_afd" del
#"afds_controlador.py". Asi que, cualquier cambio realizado aqui, tambien debe 
#considerarse si se realiza o no en la funcion "generar_afd".
#################CONSTRUCCION DEL AFN POR EL METODO DE THOMPSON#################

            #INICIALIZACION DE VARIBLES
            #Inicializamos algunas variables necesarias.
            analizador_lexico = DBSession.query(AnalizadorLexico).get(id_analizador_lexico)
            nombre_analizador = analizador_lexico.nombre_analizador_lexico
            lista_alfabetos = analizador_lexico.alfabetos
            lista_expresiones = analizador_lexico.expresiones_regulares
            mi_alfabeto = []
            lista_de_tupla_nombre_definicion = []
            lista_final_definicion_expresiones = []
            mi_diccionario_alfa = {}
            mi_diccionario_expr = {}
            mi_diccionario_operadores = {"(":"(",")":")","*":"*","+":"+","?":"?",".":".","|":"|"}

            #OBTENCION DEL ALFABETO Y CREACION DE SU DICCIONARIO:
            #Agrupamos todos los alfabetos del analizador lexico correspondiente,
            #eliminamos los elementos duplicados y "creamos un diccionario" con
            #la lista resultante.
            if lista_alfabetos != []:
               for alfabeto in lista_alfabetos:
                   definicion_alfabeto = alfabeto.definicion_alfabeto
                   lista_simbolos = definicion_alfabeto.split()
                   for c in lista_simbolos:
                       mi_alfabeto.append(c) #Agrupacion de alfabetos.

               mi_alfabeto = list(set(mi_alfabeto)) #Eliminacion de duplicados.
               mi_diccionario_alfa = dict.fromkeys(mi_alfabeto) #Creacion del diccionario.
            else:
               flash(_("Su analizador lexico no dispone de Alfabeto!"), 'error')
               redirect("/cadenas/analizadores_disponibles")

            #OBTENCION DE LOS NOMBRES Y DEFINICIONES DE LAS EXPRESIONES REGULARES, Y CREACION DE SU DICCIONARIO:
            #Creamos una lista con los nombres de las expresiones regulares.
            #Creamos una lista con las definiciones de las expresiones regulares.
            #"Creamos un diccionario" para las expresiones regulares, que tienen
            #por clave el nombre y por valor la definicion.
            if lista_expresiones != []:
               for expresion in lista_expresiones:
                   tupla_nombre_definicion = (expresion.nombre_expresion_regular,expresion.definicion_expresion_regular)
                   lista_de_tupla_nombre_definicion.append(tupla_nombre_definicion)
                   mi_diccionario_expr[expresion.nombre_expresion_regular] = expresion.definicion_expresion_regular #Creacion del diccionario.
            else:
               flash(_("Su analizador lexico no dispone de Expresiones Regulares!"), 'error')
               redirect("/cadenas/analizadores_disponibles")

            #En cada definicion de expresion regular, sustituimos cualquier
            #otra definicion que forme parte de esa definicion.
            if lista_de_tupla_nombre_definicion != []:
               for tupla_nombre_definicion in lista_de_tupla_nombre_definicion:
                   nombre_expresion = tupla_nombre_definicion[0]
                   definicion_expresion = tupla_nombre_definicion[1]
                   #En este "while" se buscan definiciones que se encuentran
                   #dentro de "definicion_expresion".
                   i = 0
                   while i < len(definicion_expresion):
                         c = definicion_expresion[i]
                         #En este "if" se verifica si se trata de operadores.
                         #De ser asi se continua el ciclo en la posicion siguiente.
                         if mi_diccionario_operadores.has_key(c):
                            i = i + 1
                         #En este "else" se extrae la definicion.
                         else:
                            simbolo_o_palabra = c
                            j = i + 1
                            ban = False
                            #Aqui se trata de formar la definicion encontrada.
                            if j<len(definicion_expresion):
                               while not mi_diccionario_operadores.has_key(definicion_expresion[j]):
                                     simbolo_o_palabra = simbolo_o_palabra + definicion_expresion[j]
                                     ban = True
                                     i = i + 1
                                     j = i + 1
                                     if j<len(definicion_expresion):
                                        pass
                                     else:
                                        break

                            #Se verifica que la definicion encontrada exista.
                            #Deberia existir si llega hasta aqui. De este modo se
                            #la inserta dentro de "definicion_expresion", y la busqueda
                            #se retrocede hasta la posicion donde comienza la sustitucion.
                            if ban==True:
                               if mi_diccionario_expr.has_key(simbolo_o_palabra) and simbolo_o_palabra != nombre_expresion:
                                  pos_inicial = i - len(simbolo_o_palabra) + 1
                                  pos_final = i + 1
                                  definicion_expresion = definicion_expresion[0:pos_inicial] + "(" + mi_diccionario_expr.get(simbolo_o_palabra)+ ")" + definicion_expresion[pos_final:]
                                  i = pos_inicial - 1
                               else:
                                  if simbolo_o_palabra == nombre_expresion:
                                     flash(_("Se han detectado definiciones que provocan ciclos!"), 'error')
                                     redirect("/cadenas/analizadores_disponibles")
                                  else:
                                     flash(_("Existe una definicion de expresion no valida!"), 'error')
                                     redirect("/cadenas/analizadores_disponibles")

                            i = i + 1
                   
                   t = (nombre_expresion, definicion_expresion)
                   lista_final_definicion_expresiones.append(t)

               #Eliminamos los duplicados de la lista final de las definiciones de las 
               #expresiones regulares, luego ordenamos la lista.
               #lista_final_definicion_expresiones = list(set(lista_final_definicion_expresiones))
               #lista_final_definicion_expresiones.sort()
            else:
               flash(_("Su analizador lexico no dispone de definiciones de Expresiones Regulares!"), 'error')
               redirect("/cadenas/analizadores_disponibles")


            #CONSTRUCCION DEL AFN POR EL METODO DE THOMPSON:
            numeracion_estados = 1
            tabla_transiciones = {}
            lista_i_f_por_definicion = []
            estado_inicio_aceptacion = []

            #Utilizamos la lista que contiene las expresiones regulares.
            if lista_final_definicion_expresiones != []:
               for tupla_nombre_definicion in lista_final_definicion_expresiones:
                   nombre_expresion = tupla_nombre_definicion[0]
                   definicion_expresion = tupla_nombre_definicion[1]

                   #Cada definicion transformamos a su representacion posfija.
                   definicion_posfija = infijo_a_posfijo(definicion_expresion,precedencia)

                   #Utilizamos una pila para ir construyendo la tabla de transiciones.
                   pila = Pila()
                   for c in definicion_posfija:

                       if mi_diccionario_alfa.has_key(c):
                          pila.push(c)
                       elif mi_diccionario_operadores.has_key(c):

                          #Thompson para un caracter con el operador "*".
                          if c == "*":
                             s = pila.top() 
                             pila.pop()
                             if mi_diccionario_alfa.has_key(s):
                                n1 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n2 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = (s,n2)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n1] = lista_transiciones

                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = ("",n1)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                t = ("",n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones

                                t = ("",n4)
                                lista_transiciones = tabla_transiciones[n3]
                                lista_transiciones.append(t)

                                t = ("",n1)
                                lista_transiciones = tabla_transiciones[n2]
                                lista_transiciones.append(t)
                                          
                                inicio_actual = n3
                                fin_actual = n4
                                t = (inicio_actual,fin_actual)
                                pila.push(t)
                             else:
                                n1 = s[0]
                                n2 = s[1]
                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = ("",n1)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                t = ("",n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones

                                t = ("",n4)
                                lista_transiciones = tabla_transiciones[n3]
                                lista_transiciones.append(t)

                                t = ("",n1)
                                lista_transiciones = tabla_transiciones[n2]
                                lista_transiciones.append(t)

                                inicio_actual = n3
                                fin_actual = n4
                                t = (inicio_actual,fin_actual)
                                pila.push(t)

                          #Thompson para un caracter con el operador "+".
                          elif c == "+":
                             s = pila.top() 
                             pila.pop()
                             if mi_diccionario_alfa.has_key(s):
                                n1 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n2 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = (s,n2)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n1] = lista_transiciones

                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = ("",n1)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                t = ("",n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones

                                t = ("",n4)
                                lista_transiciones = tabla_transiciones[n3]
                                lista_transiciones.append(t)

                                t = ("",n1)
                                lista_transiciones = tabla_transiciones[n2]
                                lista_transiciones.append(t)

                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = (s,n3)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n5] = lista_transiciones

                                inicio_actual = n5
                                fin_actual = n4
                                t = (inicio_actual,fin_actual)
                                pila.push(t)
                             else:
                                n1 = s[0]
                                n2 = s[1]
                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1

                                #Copiamos la transicion que va de n1 a n2 para concatenar luego,
                                #ya que a+=aa*, entonces necesitamos tener una replica de a.
                                #Primero, cargamos los nodos a recorrer.
                                pila_recorrido = Pila()
                                pila_recorrido.push(n1)
                                lista_de_nodos = []
                                while not pila_recorrido.empty():
                                      nodo = pila_recorrido.top()
                                      lista_de_nodos.append(nodo)
                                      pila_recorrido.pop()
                                      lista_nodo = tabla_transiciones[nodo]
                                      for t in lista_nodo:
                                          dest = t[1]
                                          if dest != n2:
                                             pila_recorrido.push(dest)

                                #Establecemos la nueva numeracion.
                                nueva_numeracion = {}
                                nueva_numeracion[n1] = n5
                                nueva_numeracion[n2] = n3
                                for nodo in lista_de_nodos:
                                    if nodo == n1:
                                       pass
                                    else:
                                       n = numeracion_estados
                                       numeracion_estados = numeracion_estados + 1
                                       nueva_numeracion[nodo] = n

                                #Empezamos el copiado.
                                for nodo in lista_de_nodos:
                                    lista_nodo = tabla_transiciones[nodo]
                                    lista_transiciones = []
                                    for t in lista_nodo:
                                        s = t[0]
                                        dest = t[1]
                                        nt = (s,nueva_numeracion[dest])
                                        lista_transiciones.append(nt)
                                    tabla_transiciones[nueva_numeracion[nodo]] = lista_transiciones
                                        
                                #Se unen todas las piezas.
                                t = ("",n1)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                t = ("",n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones

                                t = ("",n4)
                                lista_transiciones = tabla_transiciones[n3]
                                lista_transiciones.append(t)

                                t = ("",n1)
                                lista_transiciones = tabla_transiciones[n2]
                                lista_transiciones.append(t)

                                inicio_actual = n5
                                fin_actual = n4
                                t = (inicio_actual,fin_actual)
                                pila.push(t)

                          #Thompson para un caracter con el operador "?".
                          elif c == "?":
                             s = pila.top() 
                             pila.pop()
                             if mi_diccionario_alfa.has_key(s):
                                n1 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n2 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = (s,n2)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n1] = lista_transiciones

                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = ("",n1)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                t = ("",n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones

                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n6 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = ("",n6)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n5] = lista_transiciones

                                t = ("",n5)
                                lista_transiciones = tabla_transiciones[n3]
                                lista_transiciones.append(t)

                                t = ("",n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n6] = lista_transiciones

                                inicio_actual = n3
                                fin_actual = n4
                                t = (inicio_actual,fin_actual)
                                pila.push(t)
                             else:
                                n1 = s[0]
                                n2 = s[1]
                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = ("",n1)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                t = ("",n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones

                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n6 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = ("",n6)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n5] = lista_transiciones

                                t = ("",n5)
                                lista_transiciones = tabla_transiciones[n3]
                                lista_transiciones.append(t)

                                t = ("",n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n6] = lista_transiciones

                                inicio_actual = n3
                                fin_actual = n4
                                t = (inicio_actual,fin_actual)
                                pila.push(t)

                          #Thompson para un caracter con el operador ".".
                          elif c == ".":
                             s2 = pila.top()
                             pila.pop()
                             s1 = pila.top()
                             pila.pop()                                
                             if mi_diccionario_alfa.has_key(s1) and mi_diccionario_alfa.has_key(s2):
                                n1 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n2 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = (s2,n3)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones
                                t = (s1,n2)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n1] = lista_transiciones

                                inicio_actual = n1
                                fin_actual = n3
                                t = (inicio_actual,fin_actual)
                                pila.push(t)
                             elif mi_diccionario_alfa.has_key(s1) and mi_diccionario_alfa.has_key(s2) == False:
                                n1 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n2 = s2[0]
                                n3 = s2[1]
                                t = (s1,n2)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n1] = lista_transiciones

                                inicio_actual = n1
                                fin_actual = n3
                                t = (inicio_actual,fin_actual)
                                pila.push(t)
                             elif mi_diccionario_alfa.has_key(s1) == False and mi_diccionario_alfa.has_key(s2):
                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n1 = s1[0]
                                n2 = s1[1]
                                t = (s2,n3)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones

                                inicio_actual = n1
                                fin_actual = n3
                                t = (inicio_actual,fin_actual)
                                pila.push(t)

                             elif mi_diccionario_alfa.has_key(s1) == False and mi_diccionario_alfa.has_key(s2) == False:
                                n1 = s1[0]
                                n2 = s1[1]
                                n3 = s2[0]
                                n4 = s2[1]

                                lista_transiciones = tabla_transiciones[n3]
                                tabla_transiciones[n2] = lista_transiciones
                                tabla_transiciones.pop(n3)

                                inicio_actual = n1
                                fin_actual = n4
                                t = (inicio_actual,fin_actual)
                                pila.push(t)

                          #Thompson para un caracter con el operador "|".
                          elif c == "|":
                             s2 = pila.top()
                             pila.pop()
                             s1 = pila.top()
                             pila.pop()                  
                             if mi_diccionario_alfa.has_key(s1) and mi_diccionario_alfa.has_key(s2):
                                n1 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n2 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t = (s1,n2)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n1] = lista_transiciones
                                t = (s2,n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n6 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t1 = ("",n1)
                                t2 = ("",n3)
                                lista_transiciones = []
                                lista_transiciones.append(t1)
                                lista_transiciones.append(t2)
                                tabla_transiciones[n5] = lista_transiciones

                                t = ("",n6)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n4] = lista_transiciones

                                inicio_actual = n5
                                fin_actual = n6
                                t = (inicio_actual,fin_actual)
                                pila.push(t)
                             elif mi_diccionario_alfa.has_key(s1) and mi_diccionario_alfa.has_key(s2) == False:
                                n1 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n2 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n3 = s2[0]
                                n4 = s2[1]
                                t = (s1,n2)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n1] = lista_transiciones

                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n6 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t1 = ("",n1)
                                t2 = ("",n3)
                                lista_transiciones = []
                                lista_transiciones.append(t1)
                                lista_transiciones.append(t2)
                                tabla_transiciones[n5] = lista_transiciones

                                t = ("",n6)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n4] = lista_transiciones

                                inicio_actual = n5
                                fin_actual = n6
                                t = (inicio_actual,fin_actual)
                                pila.push(t)
                             elif mi_diccionario_alfa.has_key(s1) == False and mi_diccionario_alfa.has_key(s2):
                                n3 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n4 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n1 = s1[0]
                                n2 = s1[1]
                                t = (s2,n4)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n3] = lista_transiciones

                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n6 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t1 = ("",n1)
                                t2 = ("",n3)
                                lista_transiciones = []
                                lista_transiciones.append(t1)
                                lista_transiciones.append(t2)
                                tabla_transiciones[n5] = lista_transiciones

                                t = ("",n6)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n4] = lista_transiciones

                                inicio_actual = n5
                                fin_actual = n6
                                t = (inicio_actual,fin_actual)
                                pila.push(t)

                             elif mi_diccionario_alfa.has_key(s1) == False and mi_diccionario_alfa.has_key(s2) == False:
                                n1 = s1[0]
                                n2 = s1[1]
                                n3 = s2[0]
                                n4 = s2[1]

                                n5 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                n6 = numeracion_estados
                                numeracion_estados = numeracion_estados + 1
                                t1 = ("",n1)
                                t2 = ("",n3)
                                lista_transiciones = []
                                lista_transiciones.append(t1)
                                lista_transiciones.append(t2)
                                tabla_transiciones[n5] = lista_transiciones

                                t = ("",n6)
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n2] = lista_transiciones
                                lista_transiciones = []
                                lista_transiciones.append(t)
                                tabla_transiciones[n4] = lista_transiciones

                                inicio_actual = n5
                                fin_actual = n6
                                t = (inicio_actual,fin_actual)
                                pila.push(t)
                                  
                   t = pila.top()
                   pila.pop()
                   #Verificar si se trata de un solo caracter o no el que quedo en la pila.
                   if mi_diccionario_alfa.has_key(t):
                      n1 = numeracion_estados
                      numeracion_estados = numeracion_estados + 1
                      n2 = numeracion_estados
                      numeracion_estados = numeracion_estados + 1
                      tt = (t,n2)
                      lista_transiciones = []
                      lista_transiciones.append(tt)
                      tabla_transiciones[n1] = lista_transiciones

                      inicio_actual = n1
                      fin_actual = n2
                      tt = (inicio_actual,fin_actual)
                      lista_i_f_por_definicion.append(tt)
                   else:
                      lista_i_f_por_definicion.append(t)


               #Unimos los automatas de cada definicion, para obtener un unico AFN.
               if lista_i_f_por_definicion != [] and len(lista_i_f_por_definicion) > 1:
                  pila = Pila()           
                  for t_i_f in lista_i_f_por_definicion:
                      pila.push(t_i_f)
                      if pila.size() < 2:
                         pass
                      else:
                         t2 = pila.top()
                         pila.pop()
                         t1 = pila.top()
                         pila.pop()
                         n1 = t1[0]
                         n2 = t1[1]
                         n3 = t2[0]
                         n4 = t2[1]

                         n5 = numeracion_estados
                         numeracion_estados = numeracion_estados + 1
                         n6 = numeracion_estados
                         numeracion_estados = numeracion_estados + 1
                         t1 = ("",n1)
                         t2 = ("",n3)
                         lista_transiciones = []
                         lista_transiciones.append(t1)
                         lista_transiciones.append(t2)
                         tabla_transiciones[n5] = lista_transiciones

                         t = ("",n6)
                         lista_transiciones = []
                         lista_transiciones.append(t)
                         tabla_transiciones[n2] = lista_transiciones
                         lista_transiciones = []
                         lista_transiciones.append(t)
                         tabla_transiciones[n4] = lista_transiciones

                         inicio_actual = n5
                         fin_actual = n6
                         t = (inicio_actual,fin_actual)
                         pila.push(t)
                  
                  t = pila.top()
                  pila.pop()
                  estado_inicio_aceptacion.append(t)

               elif len(lista_i_f_por_definicion) == 1:
                  t = lista_i_f_por_definicion[0]
                  estado_inicio_aceptacion.append(t)
               else:
                  flash(_("No se pudo obtener los estados de inicio y de aceptacion! SQLAlchemyError..."), 'error')
                  redirect("/cadenas/analizadores_disponibles")

################################################################################
#############CONSTRUCCION DEL AFD CON EL ALGORITMO DE SUBCONJUNTOS##############

            #SIMBOLOS A CONSIDERAR:
            #Extraccion de los simbolos utilizados en las definiciones de las 
            #expresiones regulares.
            lista_simbolos_utilizados = []
            if lista_final_definicion_expresiones != []:
               for tupla_nombre_definicion in lista_final_definicion_expresiones:
                   nombre_expresion = tupla_nombre_definicion[0]
                   definicion_expresion = tupla_nombre_definicion[1]
                   for s in definicion_expresion:
                       if mi_diccionario_alfa.has_key(s):
                          lista_simbolos_utilizados.append(s)
                       else:
                          pass

            lista_simbolos_utilizados = list(set(lista_simbolos_utilizados)) #Eliminacion de duplicados.

            #CERRADURA-E:
            #Calculamos la cerradura-e de cada estado del AFN
            #Los terminos "nodo" y "estado" se refieren a lo mismo, indica
            #la numeracion que llevan los nodos en el grafo.
            mi_diccionario_cerradura = {}
            lista_nodos = tabla_transiciones.keys()
            pila_estados = Pila()
            t = estado_inicio_aceptacion[0]
            inicio_afn = t[0]
            aceptacion_afn = t[1]
            if lista_nodos != []:
               for nodo in lista_nodos:
                   cerradura_e = []
                   lista_transiciones = []
                   pila_estados.push(nodo)
                   while not pila_estados.empty():
                         estado = pila_estados.top()
                         pila_estados.pop()
                         cerradura_e.append(estado)
                         if estado != aceptacion_afn:
                            lista_transiciones = tabla_transiciones[estado]
                            for t in lista_transiciones:
                                s = t[0]
                                dest = t[1]
                                if s == "":
                                   pila_estados.push(dest)
                                else:
                                   pass
                   #Cargamos el diccionario para la cerradura-e de cada estado.
                   mi_diccionario_cerradura[nodo] = cerradura_e

            else:
               flash(_("No se pudo obtener la Tabla de transiciones del AFN..."), 'error')
               redirect("/cadenas/analizadores_disponibles")

            #Incluimos en el diccionario de cerraduras, al de aceptacion de afn
            cerradura_e = []
            cerradura_e.append(aceptacion_afn)
            mi_diccionario_cerradura[aceptacion_afn] = cerradura_e

            #CONSTRUCCION DE LOS SUBCONJUNTOS PARA EL AFD.
            #Inicializamos algunas variables.
            #El diccionario "tabla_subconjuntos_afd" tiene como clave la nueva
            #numeracion de los estados del AFD, y como valor una lista de los estados del AFN.
            #El diccionario "tabla_transiciones_afd" corresponde a la Tabla de transiciones
            #para el AFD con la nueva numeracion de los estados.   
            numeracion_estados_afd = 1
            tabla_subconjuntos_afd = {}
            tabla_transiciones_afd = {}
            estado_inicio_afd = []
            estados_aceptacion_afd = []

            #El estado de inicio del AFD es igual a la cerradura-e del estado
            #de inicio del AFN.
            n1 = numeracion_estados_afd
            numeracion_estados_afd = numeracion_estados_afd + 1
            tabla_subconjuntos_afd[n1] = mi_diccionario_cerradura[inicio_afn]
            estado_inicio_afd.append(n1)

            #En este "while" se crean los nodos para el AFD.
            pila_estados_afd = Pila()
            pila_estados_afd.push(n1)
            while not pila_estados_afd.empty():
                  nodo_afd = pila_estados_afd.top()
                  pila_estados_afd.pop()
                  lista_transiciones = []
                  tabla_transiciones_afd[nodo_afd] = lista_transiciones
                  for s in lista_simbolos_utilizados:
                      #Se realiza la funcionalidad mover(T,s).
                      lista_mover = []
                      subconjunto_mover = tabla_subconjuntos_afd[nodo_afd]

                      if subconjunto_mover != []:
                         for estado in subconjunto_mover:
                             if estado != aceptacion_afn:
                                lista_estado = tabla_transiciones[estado]
                                for t in lista_estado:
                                    c = t[0]
                                    destino = t[1]
                                    if c == s:
                                       lista_mover.append(destino)

                      #Utilizamos "lista_mover" que contiene el resultado de mover(T,s).
                      if lista_mover != []:
                         lista_mover = list(set(lista_mover))
                         cerradura_mover = []
                         for estado in lista_mover:
                             cerradura = mi_diccionario_cerradura[estado]
                             for es in cerradura:
                                 cerradura_mover.append(es)

                         cerradura_mover = list(set(cerradura_mover))

                         #Comprobar si ya existe el subconjunto "cerradura_mover".
                         existe_cerradura_mover = False
                         estado_afd_existente = 0
                         lista_subconjuntos = tabla_subconjuntos_afd.keys()
                         for estado_afd in lista_subconjuntos:
                             subconjunto = tabla_subconjuntos_afd[estado_afd]
                             cerradura_mover.sort()
                             subconjunto.sort()
                             #Revisar
                             cad1 = "".join(str(cerradura_mover))
                             cad2 = "".join(str(subconjunto))
                             if cad1 == cad2:
                                existe_cerradura_mover = True
                                estado_afd_existente = estado_afd
                                break

                         #Si ya existe entonces no se crea un nuevo nodo para el AFD.
                         if existe_cerradura_mover == True:
                            t = (s,estado_afd_existente)
                            lista_transiciones = tabla_transiciones_afd[nodo_afd]
                            lista_transiciones.append(t)
                         #Si no existe entonces se crea un nuevo nodo y se agrega a la pila.
                         else:
                            n = numeracion_estados_afd
                            numeracion_estados_afd = numeracion_estados_afd + 1
                            tabla_subconjuntos_afd[n] = cerradura_mover
                            t = (s,n)
                            lista_transiciones = tabla_transiciones_afd[nodo_afd]
                            lista_transiciones.append(t)
                            pila_estados_afd.push(n)


            #Establecemos los estados de aceptacion del AFD.
            estados_nuevos = tabla_subconjuntos_afd.keys()
            for estado_nuevo in estados_nuevos:
                subconjunto = tabla_subconjuntos_afd[estado_nuevo]
                for estado_afn in subconjunto:
                    if aceptacion_afn == estado_afn:
                       estados_aceptacion_afd.append(estado_nuevo)

################################################################################
############################OPTIMIZACION DEL AFD################################


            #ALGORITMO DE MINIMIZACION DE ESTADOS DE UN AFD:
            tabla_particiones_afdop = {}
            tabla_transiciones_afdop = {}
            estado_inicio_afdop = []
            estados_aceptacion_afdop = []

            #Completamos la tabla de transiciones del AFD con las transiciones
            #hacia los simbolos que faltan. El estado de error es 0.
            estado_error_afd = 0
            estados_afd = tabla_transiciones_afd.keys()
            lista_transiciones = []
            tabla_transiciones_afd[estado_error_afd] = lista_transiciones
            if estados_afd != []:
               for estado in estados_afd:
                   lista_transiciones = []
                   lista_transiciones = tabla_transiciones_afd[estado]
                   alfabeto = []
                   alfabeto = list(lista_simbolos_utilizados)

                   for t in lista_transiciones:
                       s = t[0]
                       alfabeto.remove(s)

                   for s in alfabeto:
                       t = (s,estado_error_afd)
                       lista_transiciones.append(t)
            else:
               flash(_("No se pudo obtener la Tabla de transiciones del AFD..."), 'error')
               redirect("/cadenas/analizadores_disponibles")

            #La tabla de particiones inicia con dos grupos. Uno con los estados 
            #de aceptacion y otro con los de no aceptacion.
            g1 =  numeracion_estados_afd
            numeracion_estados_afd = numeracion_estados_afd + 1
            g2 = numeracion_estados_afd
            numeracion_estados_afd = numeracion_estados_afd + 1

            #Revisar
            inicio_afd = estado_inicio_afd[0]
            dic_aceptacion = {}
            dic_aceptacion = dict.fromkeys(estados_aceptacion_afd)

            lista_aceptacion = []
            lista_no_aceptacion = []

            estados_actuales_afd = tabla_transiciones_afd.keys()
            for estado_afd in estados_actuales_afd:
                if dic_aceptacion.has_key(estado_afd):
                   lista_aceptacion.append(estado_afd)
                else:
                   lista_no_aceptacion.append(estado_afd)

            tabla_particiones_afdop[g1] = lista_aceptacion
            tabla_particiones_afdop[g2] = lista_no_aceptacion

#########################   GRAFO DEL AFD COMPLETO   ###########################

            #Generamos los grafos para el Afn resultante.
            G = pydot.Dot(graph_type='digraph')
            claves = tabla_transiciones_afd.keys()

            #El nodo de inicio coloreamos en rojo, el de aceptacion en verde.
            t = estado_inicio_aceptacion[0]
            inicio_afd = estado_inicio_afd[0]
            G.add_node(pydot.Node(str(inicio_afd), shape="circle", style="filled", fillcolor="red", fixedsize='true', width='0.35', heigth='0.35', fontsize='11', fontcolor='black'))
            G.add_node(pydot.Node(str(estado_error_afd), shape="circle", style="filled", fillcolor="black", fixedsize='true', width='0.35', heigth='0.35', fontsize='11', fontcolor='yellow'))

            #Los nodos de aceptacion coloreamos en verde.
            for ea in estados_aceptacion_afd:
                G.add_node(pydot.Node(str(ea), shape="circle", style="filled", fillcolor="green", fixedsize='true', width='0.35', heigth='0.35', fontsize='11', fontcolor='black'))

            #Revisar
            dic_aceptacion = {}
            dic_aceptacion = dict.fromkeys(estados_aceptacion_afd)

            ##Creamos los demas nodos.
            if claves != []:
               for clave in claves:
                   if clave != inicio_afd and not dic_aceptacion.has_key(clave) and clave != estado_error_afd:
                      G.add_node(pydot.Node(str(clave), shape="circle", style="filled", fillcolor="white", fixedsize='true', width='0.35', heigth='0.35', fontsize='11', fontcolor='black'))
            else:
               flash(_("No se pudo obtener las claves de la Tabla de Transiciones!"), 'error')
               redirect("/cadenas/analizadores_disponibles")

            #Creamos las aristas.
            tuplas_clave_valor = tabla_transiciones_afd.items()
            if tuplas_clave_valor != []:
               for tupla_clave_valor in tuplas_clave_valor:
                   n1 = tupla_clave_valor[0]
                   aristas = tupla_clave_valor[1]
                   if aristas != []:
                      for arista in aristas:
                          c = arista[0]
                          n2 = arista[1]
                          if c == "":
                             transicion = "ε"
                          else:
                             transicion = c
                          G.add_edge(pydot.Edge(str(n1), str(n2), label=str(transicion), fontcolor='blue', fontsize="15.0", color="black"))
                   else:
                      pass

            #Dibujamos el grafo y lo guardamos como imagen.
            G.write_png("/home/raul/tg2env/LEX/lex/public/images/afd_completo_graph.png")

################################################################################

            #Continuamos con la particion
            print tabla_particiones_afdop
            ban = False
            while(ban == False):
                 particiones = tabla_particiones_afdop.keys()
                 cant_nuevas_part = 0
                 dic_particiones = {}
                 #Creamos un diccionario de diccionario de cada particion.
                 for p in particiones:
                     lista_estados_por_particion = []
                     lista_estados_por_particion = tabla_particiones_afdop[p]
                     dic_particiones[p] = dict.fromkeys(lista_estados_por_particion)

                 for p in particiones:
                     #Obtenemos las particiones uno a uno.
                     particion_actual = p
                     lista_estados_por_particion = []
                     lista_estados_por_particion = tabla_particiones_afdop[particion_actual]
                     estados_actuales_comparados = list(lista_estados_por_particion)
                     hay_particon = bool
                     hay_particion = False
                     #No consideramos las particiones con un solo elemento.
                     if len(lista_estados_por_particion) > 1:
                         #Tomamos un estado de la particion analizada y la comparamos
                         #con el resto para saber si se puede particionar.
                         for estado in lista_estados_por_particion:
                             lista_transiciones1 = []
                             lista_transiciones1 = tabla_transiciones_afd[estado]
                             estados_actuales_comparados.remove(estado)
                             nueva_particion = []
                             #Analizamos cada transicion del estado en curso.
                             if lista_transiciones1 != []:
                                 estados_restantes = []
                                 estados_restantes = list(estados_actuales_comparados)
                                 for t1 in lista_transiciones1:
                                     s1 = t1[0]
                                     dest1 = t1[1]
                                     #Comparamos con las transiciones de los demas
                                     #estados con los que se compara el estado en curso.
                                     if estados_restantes != []:
                                         for estado_restante in estados_restantes:                                          
                                             lista_transiciones2 = []
                                             lista_transiciones2 = tabla_transiciones_afd[estado_restante]
                                             for t2 in lista_transiciones2:
                                                 s2 = t2[0]
                                                 dest2 = t2[1]
                                                 if s1 == s2:
                                                     part = dic_particiones.keys()
                                                     for i in part:
                                                         diccio = dic_particiones[i]
                                                         if diccio.has_key(dest1):
                                                             if diccio.has_key(dest2):
                                                                 if nueva_particion.count(estado_restante) < 1:
                                                                    nueva_particion.append(estado_restante)
                                                                 else:
                                                                    break
                                                             elif nueva_particion.count(estado_restante) == 1:
                                                                 nueva_particion.remove(estado_restante)
                                                                 break
                                                             else:
                                                                 break
                                                     break

                                                 else:
                                                      pass
                                         
                                         if nueva_particion != []:
                                             dic_nueva_particion = dict.fromkeys(nueva_particion)
                                             a_eliminar = []
                                             for er in estados_restantes:
                                                 if not dic_nueva_particion.has_key(er):
                                                     a_eliminar.append(er)

                                             if a_eliminar != []:
                                                 for ae in a_eliminar:
                                                     estados_restantes.remove(ae)
                                         else:
                                             break

                                     else:
                                         break


                             else:
                                 pass

                             #Se compruba si es que el estado actualmente analizado
                             #tiene con quien formar una nueva particion.
                             if nueva_particion != []:
                                 nueva_particion.append(estado)
                                 nueva_particion = list(set(nueva_particion)) #Eliminacion de duplicados.

                                 #Comprobamos si la particion ya existe
                                 dic_nueva_particion = dict.fromkeys(nueva_particion)
                                 particiones = tabla_particiones_afdop.keys()
                                 existe_particion = bool
                                 existe_particion = False
                                 for p in particiones:
                                     lista_estados_por_particion = []
                                     lista_estados_por_particion = tabla_particiones_afdop[p]
                                     existe_particion = False
                                     for e in lista_estados_por_particion:
                                         if dic_nueva_particion.has_key(e):
                                            existe_particion = True
                                            pass
                                         else:
                                            existe_particion = False
                                            break

                                     if existe_particion == True and len(nueva_particion) == len(lista_estados_por_particion):
                                        break
                                     
                                 if existe_particion == True:
                                    break

                                 cant_nuevas_part = cant_nuevas_part + 1
                                 hay_particion = True

                                 lista_estados_por_particion = []
                                 lista_estados_por_particion = tabla_particiones_afdop[particion_actual]

                                 for e in nueva_particion:
                                     lista_estados_por_particion.remove(e)

                                 gn =  numeracion_estados_afd
                                 numeracion_estados_afd = numeracion_estados_afd + 1
                                 tabla_particiones_afdop[gn] = nueva_particion

                                 break
                             #Si no tiene se le separa del grupo.
                             else:
                                 nueva_particion.append(estado)
                                 cant_nuevas_part = cant_nuevas_part + 1
                                 hay_particion = True

                                 lista_estados_por_particion = []
                                 lista_estados_por_particion = tabla_particiones_afdop[particion_actual]
                                 lista_estados_por_particion.remove(estado)

                                 gn =  numeracion_estados_afd
                                 numeracion_estados_afd = numeracion_estados_afd + 1
                                 tabla_particiones_afdop[gn] = nueva_particion
                                 break

                             

                     else:
                         pass

                     if hay_particion == True:
                         break
                     else:
                         pass

                 if cant_nuevas_part == 0:
                     ban = True
                 else:
                     pass

            print tabla_particiones_afdop

            #Buscamos el estado inicial, el de error y los estados de aceptacion del AFD minimizado.
            particiones = tabla_particiones_afdop.keys()
            estado_inicial_afdop = []
            estados_aceptacion_afdop = []
            estado_error_afdop = -1
            for p in particiones:
                lista_estados_por_particion = []
                lista_estados_por_particion = tabla_particiones_afdop[p]
                for e in lista_estados_por_particion:
                    if e == inicio_afd:
                       estado_inicial_afdop.append(p)

                    if dic_aceptacion.has_key(e):
                       estados_aceptacion_afdop.append(p)

                    if e == estado_error_afd:
                       estado_error_afdop = p

            estado_inicial_afdop = list(set(estado_inicial_afdop)) #Eliminacion de duplicados.
            estados_aceptacion_afdop = list(set(estados_aceptacion_afdop)) #Eliminacion de duplicados.
            inicio_afdop = estado_inicial_afdop[0]
            dic_aceptacion_afdop = dict.fromkeys(estados_aceptacion_afdop)

            #Creamos un diccionario de diccionario de cada particion.
            dic_particiones = {}
            for p in particiones:
                lista_estados_por_particion = []
                lista_estados_por_particion = tabla_particiones_afdop[p]
                dic_particiones[p] = dict.fromkeys(lista_estados_por_particion)

            tabla_transiciones_afdop = {}
            for p in particiones:
                lista_estados_por_particion = []
                lista_estados_por_particion = tabla_particiones_afdop[p]
                lista_transiciones = []
                tabla_transiciones_afdop[p] = lista_transiciones
                estado_representante = -1
                for e in lista_estados_por_particion:
                    if e != 0:
                       estado_representante = e
                       break
                if estado_representante != -1:
                   lista_transi = tabla_transiciones_afd[estado_representante]
                   for t in lista_transi:
                       s = t[0]
                       dest = t[1]
                       part = dic_particiones.keys()
                       for i in part:
                           diccio = dic_particiones[i]
                           if diccio.has_key(dest):
                              nt = (s,i)
                              lista_transiciones = []
                              lista_transiciones = tabla_transiciones_afdop[p]                                                        
                              lista_transiciones.append(nt)
            
###################    DIBUJO DEL GRAFO AFD OPTIMIZADO      ####################

            #Generamos los grafos para el Afn resultante.
            G = pydot.Dot(graph_type='digraph')
            claves = tabla_transiciones_afdop.keys()

            #El nodo de inicio coloreamos en rojo, el de aceptacion en verde.
            G.add_node(pydot.Node(str(inicio_afdop), shape="circle", style="filled", fillcolor="red", fixedsize='true', width='0.35', heigth='0.35', fontsize='11', fontcolor='black'))
            G.add_node(pydot.Node(str(estado_error_afdop), shape="circle", style="filled", fillcolor="black", fixedsize='true', width='0.35', heigth='0.35', fontsize='11', fontcolor='yellow'))

            #Los nodos de aceptacion coloreamos en verde.
            for ea in estados_aceptacion_afdop:
                G.add_node(pydot.Node(str(ea), shape="circle", style="filled", fillcolor="green", fixedsize='true', width='0.35', heigth='0.35', fontsize='11', fontcolor='black'))

            ##Creamos los demas nodos.
            if claves != []:
               for clave in claves:
                   if clave != inicio_afdop and not dic_aceptacion_afdop.has_key(clave) and clave != estado_error_afdop:
                      G.add_node(pydot.Node(str(clave), shape="circle", style="filled", fillcolor="white", fixedsize='true', width='0.35', heigth='0.35', fontsize='11', fontcolor='black'))
            else:
               flash(_("No se pudo obtener las claves de la Tabla de Transiciones!"), 'error')
               redirect("/cadenas/analizadores_disponibles")

            #Creamos las aristas.
            tuplas_clave_valor = tabla_transiciones_afdop.items()
            if tuplas_clave_valor != []:
               for tupla_clave_valor in tuplas_clave_valor:
                   n1 = tupla_clave_valor[0]
                   aristas = tupla_clave_valor[1]
                   if aristas != []:
                      for arista in aristas:
                          c = arista[0]
                          n2 = arista[1]
                          if c == "":
                             transicion = "ε"
                          else:
                             transicion = c
                          G.add_edge(pydot.Edge(str(n1), str(n2), label=str(transicion), fontcolor='blue', fontsize="15.0", color="black"))
                   else:
                      pass

            #Dibujamos el grafo y lo guardamos como imagen.
            G.write_png("/home/raul/tg2env/LEX/lex/public/images/afdop_graph.png")
                   
        except SQLAlchemyError:
            flash(_("No se pudo acceder a Generar Afd! SQLAlchemyError..."), 'error')
            redirect("/cadenas/analizadores_disponibles")
        except (AttributeError, NameError):
            flash(_("No se pudo acceder a Generar Afd! Hay Problemas con el servidor..."), 'error')
            redirect("/cadenas/analizadores_disponibles")

        return dict(id_analizador_lexico=id_analizador_lexico, nombre_analizador=nombre_analizador,            
                    lista_final_definicion_expresiones=lista_final_definicion_expresiones, inicio=inicio_afdop, 
                    aceptacion=estados_aceptacion_afdop, estado_error_afdop = estado_error_afdop,   
                    tabla_particiones_afdop=tabla_particiones_afdop)


#----------- Funcion que convierte una expresion infija en otra posfija---------

def infijo_a_posfijo(expr, precedencia):

    pila = Pila()
    cola = Cola()
    
    for c in expr:
        if c not in precedencia:
            cola.enqueue(c)
        elif c == ")":
            while not pila.empty():
                if pila.top() == "(":
                    pila.pop()
                    break
                else:
                    cola.enqueue(pila.top())
                    pila.pop()
        else:
            if pila.empty() or c == "(":
                pila.push(c)
            else:
                while not pila.empty() and precedencia[c] <= precedencia[pila.top()]:
                    cola.enqueue(pila.top())
                    pila.pop()
                pila.push(c)
    
    while not pila.empty():
        cola.enqueue(pila.top())
        pila.pop()

    return list(cola)

"""

            #Generamos los grafos para el Afn resultante.
            G = nx.DiGraph() 
            G.colores = {}
            claves = tabla_transiciones_afd.keys()

            #El nodo de inicio coloreamos en rojo.
            inicio_afd = estado_inicio_afd[0]
            G.add_node(inicio_afd)
            G.colores[inicio_afd] = 'red'

            #Los nodos de aceptacion coloreamos en verde.
            for ea in estados_aceptacion_afd:
                G.add_node(ea)
                G.colores[ea] = 'green'

            #Revisar
            dic_aceptacion = {}
            dic_aceptacion = dict.fromkeys(estados_aceptacion_afd)

            #Creamos los nodos.
            if claves != []:
               for clave in claves:
                   if clave != inicio_afd and not dic_aceptacion.has_key(clave):
                      G.add_node(clave)
                      G.colores[clave] = 'coral'
            else:
               flash(_("No se pudo obtener las claves de la Tabla de Transiciones del AFD!"), 'error')
               redirect("/cadenas/analizadores_disponibles")
               
            #Creamos las aristas.
            tuplas_clave_valor = tabla_transiciones_afd.items()
            if tuplas_clave_valor != []:
               for tupla_clave_valor in tuplas_clave_valor:
                   n1 = tupla_clave_valor[0]
                   aristas = tupla_clave_valor[1]
                   if aristas != []:
                      for arista in aristas:
                          c = arista[0]
                          n2 = arista[1]
                          G.add_edge(n1, n2, weight=int(1))
                   else:
                      pass

            #Dibujamos el grafo y lo guardamos como imagen.
            plt.clf()
            nx.draw_circular(G, width=1, node_color = [G.colores[v] for v in G], node_size=500)
            plt.savefig("../LEX/lex/public/images/afd_graph.png")

"""

